package dp_algorithm.nowcoder.medium;

import java.util.Scanner;

/**
 * @author bruin_du
 * @description 字符串通配符
 * https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036?
 * tpId=37&&tqId=21294&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
 * @date 2022/5/14 21:02
 **/
public class StringMatch {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String p = in.nextLine();
            int row = p.length();
            int col = s.length();
            //开辟一个多出一行和一列的数组为了方便动态规划循环
            //多开辟的数组空间保存的是空字符串的匹配情况
            boolean[][] match = new boolean[row + 1][col + 1];
            //i , j 分别代表数组的中当前元素的行和列
            //由于多开辟了数组为了保存空字符串的匹配情况
            //所以p[i - 1],s[j - 1]分别代表了正常字符串和匹配字符串中当前的字符
            //数组中的元素值match[i][j]代表i - 1和j - 1当前和之前的的字符串的匹配情况

            //空字符串和空字符串匹配,置为true
            match[0][0] = true;
            //初始化空字符串的匹配情况
            for(int i = 0 ; i < col ; i++){
                if(s.charAt(i) == '*')
                    match[0][i + 1] = true;
                else
                    break;
            }
            for(int i = 1;i <= row;i++){
                for(int j = 1;j <= col;j++){
                    //匹配字符串当前字符为'*'
                    if(s.charAt(j - 1) == '*'){
                        match[i][j] =
                                //不看'*',即当'*'出现0次,还得看p[i]和s[j - 1]的匹配情况
                                match[i][j - 1] ||
                                        //看'*',即让'*'多出现一次,还得看p[i - 1]和s[j]的匹配情况
                                        //因为'*'只匹配字母和数字,还得看当前匹配的字符是否合法
                                        (match[i - 1][j] && judgeLegal(p.charAt(i - 1)));
                    }
                    //当匹配字符串当前的字符不为'*'时
                    else{
                        match[i][j] =
                                //还得看p[i - 1]和s[j - 1]的匹配情况
                                match[i - 1][j - 1] &&
                                        //看匹配串当前的字符和正常串当前的字符是否相等
                                (s.charAt(j - 1) == p.charAt(i - 1) ||
                                        //如果匹配字符为?,还得看匹配的正常串的字符是否合法
                                        (s.charAt(j - 1) == '?' && judgeLegal(p.charAt(i - 1))));
                    }
                }
            }
            //返回数组最后一个元素的匹配情况
            //该元素就是两个字符串所有的字符都进行匹配后的最终结果
            System.out.println(match[row][col]);
        }
    }
    //判断当前字符是否合法
    private static boolean judgeLegal(char ch){
        return(Character.isLowerCase(ch) || Character.isDigit(ch) || Character.isLowerCase(ch));
    }
}
